/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-17
 * Time: 22:27
 */
public class test_10 {

    public static void main(String[] args) {
       int[] arr={2,1,5,3,6,4,8,9,7};
        int ret= LIS(arr);
        System.out.println(ret);
    }

    private static int LIS(int[] arr) {
        int n=arr.length;
        int[] dp=new int[n];
        int maxlength=1;
        dp[0]=1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i ; j++) {
                if( arr[i]> arr[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            maxlength=Math.max(maxlength,dp[i]);
        }
        return maxlength;
    }
}
